package doublePoint;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.List;
import java.util.stream.Collectors;

import static java.util.Collections.sort;

public class DoublePoint {
    /*
    给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作。
示例 1:
输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]
示例 2:
输入: nums = [0]
输出: [0]
提示:
1 <= nums.length <= 104
-231 <= nums[i] <= 231 - 1
     */
    //方法一
    public void moveZeroes(int[] nums) {
            for(int i=0;i<nums.length;i++){
                for(int j=0;j<nums.length;j++){
                    if(nums[j]==0&&j+1<nums.length){
                        int temp=nums[j];
                        nums[j]=nums[j+1];
                        nums[j+1]=temp;
                    }
                }
            }
    }
    //方法二
    public void moveZeroes2(int[] nums) {
        int count=0;
        for(int i = 0;i<nums.length;i++){
            if(nums[i]==0){
                count++;
            }else if(i==0){
                continue;
            }else{
                int temp=nums[i];
                nums[i]=nums[i-count];
                nums[i-count]=temp;
            }
        }
    }
    /*
    给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明：你不能倾斜容器。
     */
    //笨方法,消耗时间太长
    public int maxArea(int[] height) {
        int maxArea=0;
        int area=0;
        int len=0;
        int wide = 0;
        int left=0;
        int right=1;
        while(right<height.length){
            if(left==height.length-2){
                len = Math.min(height[left],height[right]);
                wide=right-left;
                area=len*wide;
                if(area>maxArea)
                    maxArea=area;
                break;
            }
            len = Math.min(height[left],height[right]);
            wide=right-left;
            area=len*wide;
            if(area>maxArea)
                maxArea=area;
            if(right==height.length-1){
                left++;
                right=left+1;
                continue;
            }
            right++;
        }
        return maxArea;
    }
    //
    public int maxArea1(int[] height) {
            int maxArea=0;
            int left=0;
            int right=height.length-1;
            while(left<right){
                if(height[left]<height[right]){
                    maxArea=Math.max(maxArea,(right-left)*height[left]);
                    left++;
                }else{
                    maxArea=Math.max(maxArea,(right-left)*height[right]);
                    right--;
                }
            }
            return maxArea;
    }
    /*
    给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
     */
    //方法一：暴力
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> lists = new ArrayList<>();
        for(int i=0;i<nums.length;i++){
            if(i-1>=0&&nums[i]==nums[i-1])
                continue;
            int sum=0-nums[i];
            for(int j=i+1;j<nums.length;j++){
                int k=nums.length-1;
                if(j>i+1&&nums[j]==nums[j-1])
                    continue;
                while(k>j&&nums[k]+nums[j]>sum)
                    k--;
                if(k==j)
                    break;
                if(nums[j]+nums[k]==sum){
                    List list = new ArrayList<>();
                    list.add(nums[i]);
                    list.add(nums[j]);
                    list.add(nums[k]);
                    lists.add(list);
                }
            }
        }
        return lists;
    }
    /*
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
输入：height = [4,2,0,3,2,5]
输出：9
     */
    public static int trap(int[] height) {
           int sum =0;
            int left = 1;
            int right = height.length-2;
            int maxLeft = height[0];
            int maxRight = height[height.length-1];
            while(left<=right){
                maxLeft=Math.max(height[left],maxLeft);
                maxRight=Math.max(height[right],maxRight);
                if(maxLeft<maxRight){
                    sum+=maxLeft-height[left];
                    left++;
                }else{
                    sum+=maxRight-height[right];
                    right--;
                }
            }
            return sum;
    }
}
